#include<stdio.h>
#define MaxSise 100
typedef struct
{
    char data[MaxSise];
    int length;
}SqString;
void StrAssign(SqString &s,char cstr[])
{
    for(int i=0;cstr[i]!='\0';i++)
        s.data[i]=cstr[i];
    s.length=i;
}
void DestroyStr(SqString &s)
{ }
void StrCopy(SqString &s,SqString t)
{
    for(int i=0;i<t.length;i++)
        s.data[i]=t.data[i];
    s.length=t.length;
}
bool StrEqual(SqString s,SqString t)
{
    bool same=true;
    if(s.length!=t.length)
        same=false;
    else
        for(int i=0;i<s.length;i++)
            if(s.data[i]!=t.data[i])
            {
                same=false;
                break;
            }
    return same;
}
int StrLength(SqString s)
{
    return s.length;
}
SqString Concat(SqString s,SqString t)
{
    SqString str;
    int i;
    str.length=s.length+t.length;
    for(i=0;i<s.length;i++)
        str.data[i]=s.data[i];
    for(i=0;i<t.length;i++)
        str.data[s.length+i]=t.data[i];
    return str;
}
SqString SubStr(SqString s,int i,int j)
{
    SqString str;
    int k;
    str.length=0;
    if(i<=0||i>s.length||j<0||i+j-1>s.length)
        return str;
    for(k=i-1;k<i+j-1;k++)
        str.data[k-i+1]=s.data[k];
    str.length=j;
    return str;
}
SqString InsStr(SqString s1,int i,SqString s2)
{
    int j;SqString str;
    str.length=0;
    if(i<=0||i>s1.length+1)
        return str;
    for(j=0;j<i-1;j++)
        str.data[j]=s1.data[j];
    for(j=0;j<s2.length;j++)
        str.data[i+j-1]=s2.data[j];
    for(j=i-1;j<s1.length;j++)
        str.data[s2.length+j]=s1.data[j];
    str.length=s1.length+s2.length;
    return str;
}
SqString DelStr(SqString s,int i,int j)
{
    int k;SqString str;
    str.length=0;
    if(i<=0||i>s.length||i+j>s.length+1)
        return str;
    for(k=0;k<i-1;k++)
        str.data[k]=s.data[k];
    for(k=i+j-1;k<s.length;k++)
        str.data[k-1]=s.data[k];
    str.length=s.length-j;
    return str;
}
SqString Repstr(SqString s,int i,int j,SqString t)
{
    int k;SqString str;
    str.length=0;
    if(i<=0||i>s.length||i+j-1>s.length)
        return str;
    for(k=0;k<i-1;k++)
        str.data[k]=s.data[k];
    for(k=0;k<t.length;k++)
        str.data[i+k-1]=t.data[k];
    for(k=i+j-1;k<s.length;k++)
        str.data[t.length+k-1]=s.data[k];
    str.length=s.length-j+t.length;
    return str;
}
void DispStr(SqString s)
{
    if(s.length>0)
    {
        for(int i=0;i<s.length;i++)
        printf("%c",s.data[i]);
    printf("\n");
    }
}
int Index(SqString s,SqString t)
{
    int i=0,j=0;
    while(i<s.length&&j<t.length)
    {
        if(s.data[i]==t.data[j])
        {
            i++;
            j++;
        }
        else{
            i=i-j+1;
            j=0;
        }
    }
    if(j>=t.length)
        return(i-t.length);
    else
        return(-1);
}
void GetNext(SqString t,int next[])
{
    int j,k;
    j=0;k=-1;next[0]=-1;
    while(j<t.length-1)
    {
        if(k==-1||t.data[j]==t.data[k])
        {
            j++;
            k++;
            next[j]=k;
        }
        else k=next[k];
    }
}
int KMPIndex(SqString s,SqString t)
{
    int next[MaxSise],i=0,j=0;
    GetNext(t,next);
    while(i<s.length&&j<t.length)
    {
        if(j==-1||s.data[i]==t.data[j])
        {
            i++;
            j++;
        }
        else j=next[j];
    }
    if(j>=t.length)
        return(i-t.length);
    else
        return(-1);
}
void GetNextval(SqString t,int nextval[])
{
    int j=0,k=-1;
    nextval[0]=-1;
    while(j<t.length)
    {
        if(k==-1||t.data[j]==t.data[k])
        {
            j++;k++;
            if(t.data[j]!=t.data[k])
                nextval[j]=k;
            else
                nextval[j]=nextval[k];

        }
        elsek=nextval[k];
    }
}
int KMPIndex1(SqString s,SqString t)
{
    int nextval[MaxSise],i=0,j=0;
    GetNextval(t,nextval);
    while(i<s.length&&j<t.length)
    {
        if(j==-1||s.data[i]==t.data[j])
        {
            j++;
            i++;
        }
        else j=nextval[j];
    }
    if(j>=t.length)
        return(i-t.length);
    else
        return(-1);
}
int main()
{
    int j;
    int next[MaxSise],nextval[MaxSise];
    SqString s,t;
    StrAssign(s,"abcabcdabcdeabcdefabcdefg");
    StrAssign(t,"abcdeabcdefab"),
    printf("串s:");DispStr(s);
    printf("串t:");DispStr(t);
    printf("简单匹配算法:\n");
    printf("t在s中的位置=%d\n",Index(s,t));
    GetNext(t,next);
    GetNextval(t,nextval);
    printf("j");
    for(j=0;j<t.length;j++)
        printf("&4d",j);
    printf("\n");
    printf("t[j]");
    for(j=0;j<t.length;j++)
        printf("%4c",t.data[j]);
    printf("\n");
    printf("next");
    for(j=0;j<t.length;j++)
        printf("%4d",next[j]);
    printf("\n");
    printf("nextval");
    for(j=0;j<t.length;j++)
        printf("%4d",nextval[j]);
    printf("\n");
    printf("KMP算法:\n");
    printf("t在s中的位置=%d\n",KMPIndex(s,t));
    printf("改进的KMP算法：\n");
    printf("t在s中的位置=%d\n",KMPIndex1(s,t));
    DestroyStr(s);DestroyStr(t);
    return 1;
}